# 递归练习
# by Nasa 2022-6-21


def recurrence(n):
    if n == 0:
        print(n)
    else:
        print(n)
        recurrence(n - 1)


def recurrence_02(n):
    # 计算从1--n的累加值
    if n == 1:
        print(n)
        return n
    print(n)
    return recurrence_02(n - 1) + n


def recurrence_03(n):
    # 计算从1--n的阶乘
    if n == 1:
        return 1
    return recurrence_03(n - 1) * n


def fibonacci(num):
    # 计算斐波那契数列的第num个数
    # 数列: 1,1,2,3,5,8,13,21,34,55......
    # num:  1,2,3,4,5,6, 7, 8, 9,10
    if num == 1 or num == 2:
        return 1
    return fibonacci(num - 1) + fibonacci(num - 2)


def fibonacci_02(num):
    # 用循环的方式计算斐波那契数列的第num个数
    if num == 1 or num == 2:
        return 1
    l = [1, 1]
    for i in range(num-2):
        l.append(l[i] + l[i + 1])
    return l[num-1]


if __name__ == '__main__':
    # print('sum', recurrence_02(3))
    # print('阶乘', recurrence_03(5))
    print('斐波那契', fibonacci(10), fibonacci_02(10))

    # num = 4
    # t1 = time.time()
    # fibonacci_02(num)
    # t2 = time.time()
    # print(t2-t1)
    # t1 = time.time()
    # fibonacci(num)
    # t2 = time.time()
    # print(t2-t1)
